package com.atguigu.distributed.lock.leecode.tree;

import com.atguigu.distributed.lock.leecode.TreeNode;

/**
 * 二叉树的最近公共祖先
 */
public class LowestCommonAncestor {
    private TreeNode ans;
    public LowestCommonAncestor(){
        this.ans = null;
    }
    private boolean dfs(TreeNode root,TreeNode p,TreeNode q){
        if(root==null){
            return false;
        }
        boolean lson = dfs(root.left,p,q);
        boolean rson = dfs(root.right,p,q);
        if((lson&&rson)||((root.data==p.data||root.data==q.data)&&(lson||rson))){
            ans = root;
        }
        return lson||rson||(root.data==p.data||root.data==q.data);
    }
    public TreeNode lowestCommonAncestor(TreeNode root,TreeNode p,TreeNode q){
        this.dfs(root,p,q);
        return this.ans;
    }
}
